package ErChaShu;


import java.util.HashMap;

/**
 * 哈夫曼树构造工具类
 */
public class HuffmanTreeUtil {

    /**
     * 计算文本数据字符出现频率,计算结果保存至哈夫曼树节点数组中
     * <p>
     * 返回有效哈夫曼节点数组	 *
     *
     * @param data  文本数据
     * @param nodes 哈夫曼树节点数组
     */
    public static HuffmanNode[] calculateFrequency(String data) {
        HuffmanNode[] nodes = new HuffmanNode[256];
        // 每个节点初始计数次数为0,ASCII码最大值为256
        for (int charInt = 0; charInt < nodes.length; charInt++) {
            nodes[charInt] = new HuffmanNode((char) charInt, 0);
        }
        // 统计每一个字符出现次数,每出现1次频率加1
        for (int i = 0; i < data.length(); i++) {
            int charInt = data.charAt(i);
            nodes[charInt].frequency++;
        }
        // 将有频次的字符往前移动
        int cnt = 0;
        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i].frequency > 0) {
                nodes[cnt++] = nodes[i];
            }
        }

// 保留有频次的节点数据
        HuffmanNode[] huffmanNodes = new HuffmanNode[cnt];
        for (int i = 0; i < huffmanNodes.length; i++) {
            huffmanNodes[i] = nodes[i];
        }

// 返回有效节点数据
        return huffmanNodes;
    }

    /**
     * @param trees 字符串频率统计节点数组,可以将每一个节点看作一颗只有根节点的树
     * @return
     */
    public static HuffmanNode buildHuffmanTree(HuffmanNode[] trees) {
        int size = trees.length;
        HuffmanNode[] newTrees = new HuffmanNode[size];
        // 对传入的树按照根节点权重进行排序
        for (int i = 0; i < trees.length; i++) {
            HuffmanTreeUtil.insertAndSort(newTrees, trees[i], i);
        }
        // 构造哈夫曼树轮次
        int retCnt = 1;
        while (size > 1) {
            // 合并两棵根节点值最小的树后生成新的树，合并后二叉树总棵数减1
            HuffmanNode[] tempTrees = new HuffmanNode[size - 1];
            // 将第1棵树和第2棵树进行合并，合并后的树根节点权重等于两棵子树的权重
            int newFrequency = newTrees[0].frequency + newTrees[1].frequency;
            tempTrees[0] = new HuffmanNode('\0', newFrequency);
            // 设置新的根节点左右孩子节点
            tempTrees[0].left = newTrees[0];
            tempTrees[0].right = newTrees[1];
            // 删除已合并的树，并对新合并的树按照根节点权重进行排序
            for (int index = 2; index < size; index++) {
                HuffmanTreeUtil.insertAndSort(tempTrees, newTrees[index], index - 1);
            }
            // 刷新森林
            newTrees = tempTrees;
            // 森林中二叉树总数减1
            size--;
        }
        return newTrees[0];
    }


    /**
     * 插入节点并排序
     *
     * @param nodes 写入数组
     * @param node  待插入节点
     * @param index 写入位置下标
     */
    public static void insertAndSort(HuffmanNode[] nodes, HuffmanNode node, int index) {
        // 直接写入节点
        nodes[index] = node;
        // 向前找比自己大的节点并与之交换位置
        for (int i = index; i > 0 && nodes[i - 1].frequency > nodes[i].frequency; i--) {
            HuffmanNode temp = nodes[i - 1];
            nodes[i - 1] = nodes[i];
            nodes[i] = temp;
        }
    }

    /**
     * 计算字符编码映射字典,结果放进字典中,形如{A=101, B=1000, C=1001, D=00, E=01, F=11}
     *
     * @param root           哈夫曼树根节点
     * @param code           初始前缀
     * @param huffmanCodeMap 字符编码映射字典
     */
    public static void generateCodes(HuffmanNode root, String code, HashMap<Character, String> huffmanCodeMap) {
        // 叶子节点即为被编码字符
        if (root.left == null && root.right == null) {
            huffmanCodeMap.put(root.data, code);
        }
        // 往左子树走编码前缀加一个字符'0'
        if (root.left != null) {
            generateCodes(root.left, code + "0", huffmanCodeMap);
        }
        // 往右子树走编码前缀加一个字符'1'
        if (root.right != null) {
            generateCodes(root.right, code + "1", huffmanCodeMap);
        }
    }


    /**
     * 生成字符串二进制编码
     *
     * @param text           待编码字符串
     * @param huffmanCodeMap 字符编码映射字典,<Key,Value>结构
     * @return
     */
    public static String encodeText(String text, HashMap<Character, String> huffmanCodeMap) {
        StringBuilder encodedText = new StringBuilder();
        // 访问字符串每一个字符，将每一个字符的编码依次拼接
        char[] chArray = text.toCharArray();
        for (char c : chArray) {
            // 拼接每一个字符编码
            encodedText.append(huffmanCodeMap.get(c));
        }
        // 返回拼接结果
        return encodedText.toString();
    }

    /**
     * 解码已编码的字符
     *
     * @param encodedText 待解码字符
     * @param root        哈夫曼树根节点,约定二叉树往左走表示0,往右走表示1
     * @return
     */
    public static String decode(String encodedText, HuffmanNode root) {
        StringBuilder decodedText = new StringBuilder();
        HuffmanNode current = root;
        for (char bit : encodedText.toCharArray()) {
            if (bit == '0') {
                current = current.left;
            } else {
                current = current.right;
            }
            if (current.left == null && current.right == null) {
                decodedText.append(current.data);
                current = root;
            }
        }
        return decodedText.toString();
    }
}

